package org.algorithm.二师兄.链表;

import org.algorithm.common.ListNode;
public class 合并2个链表 {

    /***
     *
     *   输入：1->2->4, 1->3->4
     *   输出：1->1->2->3->4->4
     *
     * @param args
     */

    public static void main(String[] args) {
        ListNode listNode = ListNode.build(1,2,4);
        ListNode listNode1 = ListNode.build(1,3,4);

        ListNode listNode2 = mergeTwoListNode(listNode, listNode1);
        ListNode.print(listNode2);
    }

    private static ListNode mergeTwoListNode(ListNode head, ListNode tail) {
        // 创建一个空链表，虚拟头结点, 每次都替换当前链表所在指针
        ListNode dummy = new ListNode(-1); ListNode current = dummy;
        while (head != null && tail != null) {
            if (head.val > tail.val) {
                current.next = tail;
                tail = tail.next;
            }else {
                current.next = head;
                head = head.next;
            }
            current = current.next;
        }
        // 解决长度不一和替换总会剩一个没有替换的情况问题
        current.next = head != null ? head : tail;
        return dummy.next;
    }


}
